package com.tucc.hello.leetcode.no1_400.no1_200.no103;

import com.tucc.hello.tree.Main;
import com.tucc.hello.tree.TreeNode;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = Main.makeTree(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15));
        List<List<Integer>> result = solution.zigzagLevelOrder(root);
        System.out.println(result);
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<TreeNode>[] nodes = new List[2];
        nodes[0] = new ArrayList<>();
        nodes[1] = new ArrayList<>();
        int cur = 0;
        nodes[0].add(root);
        boolean queue;
        while (true) {
            int left = cur % 2;
            queue = left == 0;
            List<TreeNode> now = nodes[left];
            if (now.isEmpty()) {
                break;
            }
            List<TreeNode> another = nodes[1 - left];
            List<Integer> list = new ArrayList<>();
            Integer[] nums = new Integer[now.size()];
            for(int i = 0;i < now.size();i ++){
                TreeNode node = now.get(i);
                if(node.left != null) {
                    another.add(node.left);
                }
                if(node.right != null){
                    another.add(node.right);
                }
                int numIndex = i;
                if(!queue){
                    numIndex = now.size() - i - 1;
                }
                nums[numIndex] = node.val;
            }
            list.addAll(Arrays.asList(nums));
            now.clear();
            result.add(list);
            cur++;
        }
        return result;
    }
}
